| |
| description |
93 pages
|
|
Kurzfassung in Deutsch: Wir haben eine Konstruktion inverser Monoide
$FIM(\Gamma)/P$ und $IM(G)/P$, beruhend auf Arbeiten von Birget und
Rhodes sowie Margolis und Meakin betrachtet und konnten für diese
speziellen Klassen inverser Monoide mit idempotenter Präsentation
die Entscheidbarkeit des Wortproblems in linearer Zeit (auf einer
RAM) zeigen. Ferner ist das uniforme Wortproblem für diese inversen
Monoide EXPTIME-vollständig.
Wir haben ferner die relationale Struktur $\C(\IM(G)/P)$ mit
Prädikat $\reach_L$ betrachtet. Hierfür konnten wir die FO-Theorie
auf die MSO-Theorie des Cayeyleygraphen von $G$ reduzieren und haben
damit die Entscheidbarkeit der FO-Theorie von $\C(\IM(G)/P)$
erhalten. Diese impliziert, wie wir in Kapitel \ref{rationale
mengen} gesehen haben, eine Reihe weiterer Resultate, insbesondere
die Entscheidbarkeit des verallgemeinerten Wortproblems für
$\IM(G)/P$ sowie die Entscheidbarkeit des Leerheitsproblems für
boolesche Kombinationen rationaler Mengen in $\IM(G)/P$. Es stellt
sich die Frage, für welche Monoide $M$ die Struktur $\C(M)$ noch
entscheidbar ist, bzw. für welche Monoide Unentscheidbarkeit
gezeigt werden kann.
Kurzfassung in Englisch: We focus here on a special class of monoids
-- inverse monoids, which lie somewhere between monoids and groups.
As groups arise naturally as bijections over a set, inverse monoids
arise as monoids of partially defined injections over a set. We
consider a special kind of inverse monoids following Birget and
Rhodes (and Margolis and Meakin) and denote this inverse monoid by
$IM(G)/P$ ($FIM(\Gamma)/P$).
We show that the word problem for these inverse monoids is
decidable. Moreover the uniform word problem ist EXPTIME-complete.
Furthermore we consider a relational structure $C(IM(G)/P)$ with a
predicate $reach_L$ for any rational set $L$ in $IM(G)/P$ and show
that the first-order theory for this monoid is decidable. Same
further decidablility results follow.
|
| publisher |
Stuttgart, Germany, Universität Stuttgart
|
| type |
Text
|
| Doctoral Thesis
|
| source |
ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/DIS-2006-05/DIS-2006-05.pdf
|
| contributor |
FMI, Theoretische Informatik
|
| format |
application/pdf
|
| 536166 Bytes
|
| subject |
Complexity Measures and Classes (CR F.1.3)
|
| Mathematical Logic (CR F.4.1)
|
| Entscheidbarkeit
|
| inverse Monoide
|
| rationale Mengen
|